import { LinedListQueue } from 'data-structure/linkedList/LinkedListQueue'
import { LinkedListStack } from 'data-structure/linkedList/LinkedListStack'

export interface TreeNodeInter<E = any> {
  e: number,
  left: TreeNode<E> | null,
  right: TreeNode<E> | null,
}

export interface Compareable<E> {
  // setCompareValue(v: number): void
  getCompareValue(): number
  /**
   * NOTE: 必须手动实现比较的方法
   * 0 => 相等
   * 1 => 大于
   * -1 => 小于
   */
  compare(node: E): 0 | 1 | -1
}

export class TreeNode<E = any> implements TreeNodeInter<E>, Compareable<TreeNode> {
  // interface
  public left: TreeNode<E> | null = null
  public right: TreeNode<E> | null = null
  public e!: number
  private count: number = 1
  // 该元素在那一层
  private depth: number = 0
  // 以该元素为根的树有多少个元素
  private size: number = 0
  constructor(e: number, left: TreeNode<E>['left'] = null, right: TreeNode<E>['right'] = null) {
    this.e = e
    this.left = left
    this.right = right
  }

  public compare(node: TreeNode): 0 | 1 | -1 {
    let r: 0 | 1 | -1 = 1
    if (this.getCompareValue() > node.getCompareValue()) {
      r = 1
    } else if (this.getCompareValue() < node.getCompareValue()) {
      r = -1
    } else {
      r = 0
    }
    return r
  }

  /**
   * setCount
   */
  public setCount() {
    this.count++
  }

  /**
   * getSize
   */
  public getSize() {
    return this.size
  }

  /**
   * getDepth
   */
  public getDepth() {
    return this.depth
  }

  /**
   * setDepth
   */
  public setDepth(depth: number) {
    this.depth = depth
  }

  // /**
  //  * setSize
  //  */
  // public setSize(size: number) {

  // }

  /**
   * getCount
   */
  public getCount() {
    return this.count
  }

  public getCompareValue(): number {
    return this.e
  }
}

/**
 * 二分搜索树, 存储的数据必须要有可比较性
 * 1. 一个二叉树,
 * 2. 每一个节点的值: 大于其左子树的所有的值, 小于其右子树的所有的值
 * 3. 每一颗子树都是二分搜索树
 */
export class BinarySearchTree<E = any> {

  private root!: TreeNode<E>
  private size: number = 0
  constructor(root?: TreeNode<E>) {
    this.root = root!
    if (root) {
      this.size = 1
    }
  }

  /**
   * isEmpty
   */
  public isEmpty() {
    return this.size === 0
  }

  /**
   * floor: 寻找前驱
   */
  public floor() {
    // TODO: todo
  }

  /**
   * ceil: 寻找后继
   */
  public ceil() {
    // TODO: todo
  }

  /**
   * rank: 元素的排名
   */
  public rank() {
    // TODO: todo
  }

  /**
   * select: 根据排名来查找元素
   */
  public select() {
    // TODO: todo
  }

  /**
   * add
   */
  public add(newNode: TreeNode<E>) {
    this.root = this.addNode(this.root, newNode)
  }

  /**
   * removeMaxNode: 删除最大值的节点
   */
  public removeMax(): TreeNode<E> {
    let node = this.maximum()

    // 删除以 root 为根节点的树中删除 node
    this.root = this.removeMaxTreeNode(this.root)

    return node
  }

  /**
   * removeMinNode: 删除最小值的节点
   */
  public removeMin(): TreeNode<E> {
    let node = this.minimum()

    // 删除以 root 为根节点的树中删除 node
    this.root = this.removeMinTreeNode(this.root)

    return node
  }

  /**
   * remove: 删除任意的元素
   */
  public remove(node: TreeNode<E>) {
    this.root = this.removeTreeNode(this.root, node) as TreeNode
  }

  /**
   * minimum: 查找最小元素
   */
  public minimum(): TreeNode<E> {
    return this.minimunTree(this.root)
  }

  /**
   * maximum: 查找最大元素
   */
  public maximum(): TreeNode<E> {
    return this.maximunTree(this.root)
  }

  /**
   * levelOrder: 层序遍历: (广度优先遍历: 更快的查找到对应的元素)
   */
  public levelOrder() {
    const q = new LinedListQueue<TreeNode<E>>()
    q.enqueue(this.root)
    while (!q.isEmpty()) {
      let cur = q.dequeue()
      console.log(cur.e)
      if (cur.left) {
        q.enqueue(cur.left)
      }
      if (cur.right) {
        q.enqueue(cur.right)
      }
    }
  }

  /**
   *  preorder: 深度优先遍历[前序遍历(递归)];
   */
  public preOrderRecursion() {
    this.preOrderTreeRecursion(this.root)
  }

  /**
   * preorder: 非递归的实现
   */
  public preOrder() {
    if (!this.root) {
      return
    }
    const stack = new LinkedListStack<TreeNode>()
    stack.push(this.root)
    while (!stack.isEmpty()) {
      let node = stack.pop()
      console.log(node.e)
      if (node.right) {
        stack.push(node.right)
      }

      if (node.left) {
        stack.push(node.left)
      }
    }
  }

  /**
   * inOrder: 深度优先遍历: [中序遍历(递归实现)] 得到的结果是一个有序的序列,
   */
  public inOrderRecursion() {
    this.inOrderTreeRecursion(this.root)
  }

  /**
   * postOrderRecursion: 深度优先遍历: 后序遍历(递归实现)
   */
  public postOrderRecursion() {
    this.postOrderTreeRecursion(this.root)
  }

  /**
   * contains
   */
  public contains(node: TreeNode<E>): boolean {
    return this.containsNode(this.root, node)
  }

  private removeTreeNode(node: TreeNode<E>, delNode: TreeNode<E>): TreeNode<E> | null | void {
    if (!node) {
      return null
    }
    if (node.compare(delNode) < 0) { // 在左子树
      node.left = this.removeTreeNode(node.left!, delNode) as TreeNode
    } else if (node.compare(delNode) > 0) { // 在右子树
      node.right = this.removeTreeNode(node.right!, delNode) as TreeNode
    } else { // 找到了对应的节点
      this.size--
      if (!node.left) {
        let right = node.right
        node.right = null
        return right
      }
      if (!node.right) {
        let left = node.left
        node.left = null
        return left
      }
      // 左右子树都存在的话, 需找到当前节点的后继中
      let min = this.minimunTree(node.right)
      // 这里进行了 size--; 实际上这里是寻找子树的新的根节点
      min.right = this.removeMinTreeNode(node.right)
      // 所以这里要 size++
      this.size++
      min.left = node.left
      node.left = node.right = null
      return min
    }
  }

  private removeMaxTreeNode(node: TreeNode<E>): TreeNode<E> {
    if (!node.right) {
      let left = node.left
      node.left = null
      this.size--
      return left!
    }
    node.right = this.removeMaxTreeNode(node.right)
    return node
  }

  // 删除: node, 放回删除节点后的新的树
  private removeMinTreeNode(node: TreeNode<E>): TreeNode<E> {
    if (!node.left) {
      let right = node.right
      node.right = null
      this.size--
      return right!
    }
    node.left = this.removeMinTreeNode(node.left)
    return node
  }

  private minimunTree(node: TreeNode<E>): TreeNode<E> {
    if (!node.left) {
      return node
    }
    return this.minimunTree(node.left)
  }

  private maximunTree(node: TreeNode<E>): TreeNode<E> {
    if (!node.right) {
      return node
    }
    return this.maximunTree(node.right)
  }

  private postOrderTreeRecursion(node: TreeNode<E>) {
    if (!node) {
      return
    }

    this.postOrderTreeRecursion(node.left!)
    this.postOrderTreeRecursion(node.right!)
    console.log(node.e)
  }

  private inOrderTreeRecursion(node: TreeNode<E>) {
    if (!node) {
      return
    }

    this.inOrderTreeRecursion(node.left!)
    console.log(node.e)
    this.inOrderTreeRecursion(node.right!)
  }

  private preOrderTreeRecursion(node: TreeNode<E>) {
    if (!node) {
      return
    }
    console.log(node.e)
    this.preOrderTreeRecursion(node.left!)
    this.preOrderTreeRecursion(node.right!)
  }

  private containsNode(node: TreeNode<E>, newNode: TreeNode<E>): boolean {
    if (!node) {
      return false
    }
    if (newNode.compare(node) > 0) {
      return this.containsNode(node.right!, newNode)
    } else if (newNode.compare(node) < 0) {
      return this.containsNode(node.left!, newNode)
    }
    return true
  }

  private addNode(node: TreeNode<E>, newNode: TreeNode<E>): TreeNode<E> {
    if (!node) {
      this.size++
      return newNode
    }
    // 大于当前根节点
    if (newNode.compare(node) > 0) {
      node.right = this.addNode(node.right!, newNode)
      // 小于
    } else if (newNode.compare(node) < 0) {
      node.left = this.addNode(node.left!, newNode)
      // 等于
    } else {
      node.setCount()
    }
    return node
  }
}
